package sort;

import com.sun.istack.internal.NotNull;

/**
 * @Author: Ma JiBin
 * @Email: 1423553596@qq.com
 * @Date: 2018/10/31 15:22
 * @Description: 堆排序算法
 * 完全二叉树：二叉树叶子节点排列按照从左到右的规则
 * 堆：分为大顶堆和小顶堆
 * 大顶堆：父节点大于叶子节点的完全二叉树，最大的值在根节点
 * 小顶堆：父节点小于叶子节点的完全二叉树，最小的值在根节点
 * 一般升序排序利用大顶堆，降序排列利用小顶堆
 * 堆排序算法思想（以升序排序为例）：先将数组看做一个二叉树，从最后一个非叶子节点开始，比它的值与其叶子节点的大小
 * 将较大的值转移到父节点上，再找出倒数第二个非叶子节点，重复以上操作，直至将数组中最大的数转移到根节点，即数组下标为0的位置
 * 再将数组首尾数值对换，就将数组中的最大值转移到了数组末尾。
 * 再去掉数组末尾，重复以上操作，直至排序完成
 */
public class HeapSort {

    /**
     * 把数组中最大的值转移到堆的根节点上，再与下标为index的节点对换数值
     *
     * @param arr 待排序数组
     * @param end 数组未排序的最后一个下标
     * @param index 记录数组未排序的最后一个下标，次值一直保持不变，将数组中最大值转移到堆的根节点时，将根节点与此节点对调
     */
    public static void sort(int[] arr, int end, int index) {
        if (end <= 0) {
            int a = arr[0];
            arr[0] = arr[index];
            arr[index] = a;
            return;
        }
        //获取最后一个非叶子节点的下标及其数值
        int lastParent = (end + 1) / 2 - 1;
        int lastParentValue = arr[lastParent];

        //获取其叶子节点下标及其数值
        int son1 = lastParent * 2 + 1;
        //较大子节点下标
        int bigSon = son1;
        //记录其叶子节点个数
        int sonSum = 1;

        //判断它是否有右子节点
        if ((lastParent * 2 + 2) <= end) {
            int son2 = lastParent * 2 + 2;
            bigSon = arr[son1] > arr[son2] ? son1 : son2;
            sonSum = 2;
        }

        //比较较大的子节点与父节点的值大小，如果父节点值较小，则交换
        if (lastParentValue < arr[bigSon]) {
            arr[lastParent] = arr[bigSon];
            arr[bigSon] = lastParentValue;
        }

        //printArray(arr);

        //递归调用,减去其叶子节点
        sort(arr, end - sonSum, index);
    }

    /**
     * 去掉数组末尾值后，再调用sort方法
     * @param arr
     * @param end
     * @param start
     */
    public static void headSort(int[] arr, int end, int start) {

        while (start < end) {
            //一次调用，只能将数组下标为0-end的值中最大的一个，转移到下标为end的位置上
            sort(arr, end, end);
            end--;
        }
    }

    /**
     * 打印数组
     *
     * @param s
     */
    private static void printArray(@NotNull int[] s) {
        System.out.print("\n下标:");
        for (int p = 0; p < s.length; p++) {
            System.out.printf("%2d,", p);
        }
        System.out.print("\n数值:");
        for (Integer m : s) {
            System.out.printf("%2d,", m);
        }
        System.out.print("\n-----------------------------");
    }


    public static void main(String[] args) {
        int[] arr = {5, 4, 7, 6, 2, 3, 1};
        printArray(arr);
        headSort(arr, arr.length - 1, 0);
        printArray(arr);
    }
}
